The run time complexity of state-of-the-art inference algorithms ingraph-based dependency parsing is super-linear in the number of input words(n). Recently, pruning algorithms for these models have shown to cut a largeportion of the graph edges, with minimal damage to the resulting parse trees.Solving the inference problem in run time complexity determined solely by thenumber of edges (m) is hence of obvious importance. We propose such an inference algorithm for first-order models, which encodesthe problem as a minimum spanning tree (MST) problem in an undirected graph.This allows us to utilize state-of-the-art undirected MST algorithms whose runtime is O(m) at expectation and with a very high probability. A directed parsetree is then inferred from the undirected MST and is subsequently improved withrespect to the directed parsing model through local greedy updates, both stepsrunning in O(n) time. In experiments with 18 languages, a variant of thefirst-order MSTParser (McDonald et al., 2005b) that employs our algorithmperforms very similarly to the original parser that runs an O(n^2) directed MSTinference.
展开▼
